from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        candidates.reverse()
        print(candidates)
        can = candidates
        ret = list()
        n = len(can)

        for i in range(0, n):
            if i > 0 and can[i] == can[i-1]:
                continue
            if can[i] > target:
                continue


            if can[i] == target:
                if i > 0 and can[i] == can[i-1]:
                    continue
                ret.append([can[i]])
                continue
            
            pend = [can[i]]
            p = i+1
            last_ok = False
            while p < n:

                print('debug 2', pend, can[p])
                if sum(pend) + can[p] < target:
                    print('b 1')
                    pend.append(can[p])
                    last_ok = False
                elif sum(pend) + can[p] == target:
                    print('b 2')
#print(pend, can[p], p > i + 1, last_ok, not(can[p - 1] == can[p] and last_ok))
                    if p > i+1 and can[p-1] == can[p] and last_ok:
                        pass
                    else:
                        ret.append([*pend, can[p]])
                        pend = [can[i]]
                        last_ok = True
                else:
                    print('b 3')
#pend = [can[i]]
                    last_ok = False
                p += 1
        return ret
    
    def __init__(self) -> None:
        self.val = []
        self.tb = []

    def do_combinationSum3(self, can: List[int], target: int, result: List[int]) -> List[List[int]]:
        if target == 0:
            self.val.append(result[:])
            return
        
        p = 0
        while target > 0 and p < len(can):
            if p > 0 and can[p-1] == can[p]:
                p+=1
                continue
            result.append(can[p])
            self.do_combinationSum3(can[p+1:], target-can[p], result)
            result.pop()
            p += 1
            
            
    def combinationSum3(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
 
        can = candidates
        self.do_combinationSum3(can, target, [])
        return self.val

                

            


if __name__ == '__main__':
    print('''组合总和II: 这个题，注意审题，需要多多
一开始没有进行子问题分解，使用3数之和的方法，用普通循环搞了很久''')
    test = {
  8 : [ 10, 1, 2, 7, 6, 1, 5 ],
      5 : [ 2, 5, 2, 1, 2 ],
          1 : [ 1, 1 ],
              2 : [ 1, 1 ],
                  4 : [ 2, 2, 2 ],
                      6 : [ 4, 4, 2, 1, 4, 2, 2, 1, 3 ]
        }
    for k, v in test.items():
        print('---', k, v)
        ret = Solution().combinationSum3(v, k)
        print(ret)
